/**
    题目:
          对链表进行插入排序。
    思路:
        常规操作
    
*/
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        if(!head){
            return head;
        }
        auto one = new ListNode(0);
        auto temp = one;
        for(auto p=head; p!=NULL; p=temp) {
            auto q=one;
            for(; q->next!=NULL && p->val > q->next->val; q=q->next);
            temp = p->next;
            p->next = q->next;
            q->next = p;
        }
        return one->next;
    }
};